#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

/**
 * de Casteljau 算法实现（非递归，迭代版，与Python逻辑一致）
 * @param t 曲线参数（0 ≤ t ≤ 1）
 * @param ctrl_pts 控制点数组，格式为 {{x0,y0}, {x1,y1}, ..., {xn,yn}}
 * @param n_pts 控制点数量（n_pts = 次数 + 1）
 * @param result 输出参数，存储计算得到的曲线点 {x, y}
 * @return 0 成功，-1 失败（参数错误）
 */
int de_casteljau(double t, const double ctrl_pts[][2], int n_pts, double result[2]) {
    // 1. 参数合法性校验
    if (t < 0.0 - 1e-10 || t > 1.0 + 1e-10) { // 浮点容错
        fprintf(stderr, "错误：t = %.6f 超出 [0, 1] 范围\n", t);
        return -1;
    }
    if (n_pts < 1) {
        fprintf(stderr, "错误：控制点数量不能小于1\n");
        return -1;
    }
    if (result == NULL) {
        fprintf(stderr, "错误：result 指针为空\n");
        return -1;
    }

    // 2. 拷贝控制点到临时数组（避免修改原数据）
    double* pts = (double*)malloc(n_pts * 2 * sizeof(double));
    if (pts == NULL) {
        fprintf(stderr, "错误：内存分配失败\n");
        return -1;
    }
    for (int i = 0; i < n_pts; i++) {
        pts[i * 2] = ctrl_pts[i][0];    // x 坐标
        pts[i * 2 + 1] = ctrl_pts[i][1];// y 坐标
    }

    // 3. 逐层线性插值（复刻Python的循环逻辑）
    int n = n_pts - 1; // 曲线次数 = 控制点数量 - 1
    for (int r = 1; r <= n; r++) {
        int current_count = n - r + 1; // 当前层的点数量
        for (int i = 0; i < current_count; i++) {
            // 计算 x 坐标：(1-t)*pts[i] + t*pts[i+1]
            pts[i * 2] = (1 - t) * pts[i * 2] + t * pts[(i + 1) * 2];
            // 计算 y 坐标：(1-t)*pts[i] + t*pts[i+1]
            pts[i * 2 + 1] = (1 - t) * pts[i * 2 + 1] + t * pts[(i + 1) * 2 + 1];
        }
    }

    // 4. 提取结果（最终只剩一个点）
    result[0] = pts[0]; // x
    result[1] = pts[1]; // y

    // 5. 释放临时内存
    free(pts);
    return 0;
}

// ===================== 测试用例 =====================
int main() {
    // 示例：3 次 Bézier 曲线（4 个控制点）
    const double ctrl_pts[][2] = {
        {1.0, 0.0},   // P0
        {2.0, 3.0},   // P1
        {3.0, -1.0},  // P2
        {4.0, 5.0}    // P3
    };
    int n_pts = sizeof(ctrl_pts) / sizeof(ctrl_pts[0]); // 控制点数量：4

    // 测试参数 t = 0.5
    double t = 0.5;
    double point[2];
    int ret = de_casteljau(t, ctrl_pts, n_pts, point);

    if (ret == 0) {
        printf("t = %.2f 对应的曲线点：(%.6f, %.6f)\n", t, point[0], point[1]);
    }

    // 测试多个 t 值
    double t_values[] = {0.0, 0.25, 0.5, 0.75, 1.0};
    int n_t = sizeof(t_values) / sizeof(double);
    printf("\n多个 t 值的曲线点：\n");
    for (int i = 0; i < n_t; i++) {
        double t = t_values[i];
        double p[2];
        if (de_casteljau(t, ctrl_pts, n_pts, p) == 0) {
            printf("t = %.2f: (%.6f, %.6f)\n", t, p[0], p[1]);
        }
    }

    return 0;
}